#include "sort.h"

void bubbleSort(int *array, int N)
{

	int i = 0, k =0, swapped = 0;
	for(i=N-1;i>0;i--)
	{
		for(k=0;k<i;k++)
		{
			if(array[k]>array[k+1])
			{
				int tmp = array[k];
				array[k] = array[k+1];
				array[k+1] = tmp;
				swapped = 1;
			}
		}

		if(!swapped)
			break;
	}
}


void insertSort(int *array, int N)
{
	int i = 0, k = 0, tmp = 0;
	for(i=1;i<N;i++)
	{
		tmp = array[i];
		for(k=i-1;k>=0;k--)
		{
			if(array[k]>tmp)
				array[k+1] = array[k];
			else
				break;
		}

		array[k+1] = tmp;
	}
}


void shellSort(int *array, int N)
{
	int i =0, k=0, tmp = 0, gap = 0;

	for(gap=N/2;gap>0;gap=gap/2)
	{
		for(i=gap;i<N;i++)
		{
			tmp = array[i];
			for(k=i-1;k>=0;k--)
			{
				if(array[k]>tmp)
					array[k+1] = array[k];

				else 
					break;
			}

			array[k+1] = tmp;
		}
	}
}

static void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

static int findPivot(int *array, int left, int right)
{
	int center = (left+right)/2;
	if(array[left]>array[right])
		swap(&array[left], &array[right]);
	if(array[left]>array[center])
		swap(&array[left], &array[center]);
	if(array[center]>array[right])
		swap(&array[center], &array[right]);

	swap(&array[center], &array[right]);
	
	return array[right];
}

void quickSort(int *array, int left, int right)
{
	if(left<right)
	{
		int pivot = findPivot(array, left, right);
		int i=left, j=right;
		
		for(;;)
		{
			while(array[++i]<pivot){}
			while(array[--j]>pivot){}
			
			if(i<j)
				swap(&array[i], &array[j]);
			else
				break;
		}

		swap(&array[i], &array[right]);
	
		quickSort(array, left, i-1);
		quickSort(array, i+1, right);
	}
}

